ターゲットに関する雲状３ｄデータ点群の複数のフレームを記録する方法。

专利摘要:
雲状に分布する3次元（3D）データ点群（雲状3Dデータ点群）（200−i、200−j）の2つ以上のフレームを記録する方法が開示される。第1のフレーム（フレームi）及び第2のフレーム（フレームj）の各々の密度画像を使用して、画像と画像毎の点の対応関係を示す変換ベクトルを求める。隣接するフレーム各々の対応関係は、「フィルタリングされた密度画像」の相関を用いて決定される。1つ以上の変換ベクトルを利用して、XY平面及びZ軸方向の内の1つ以上において、雲状3Dデータ点群の粗い記録を実行する。本方法は、雲状3Dデータ点群（200−i、200−j）に適用する細かい記録プロセスも含む。（隣接するフレームだけでなはない）フレーム同士の対応する変換内容は蓄積され、「グローバル」最適化ルーチンにおいて使用され、全てのフレームの変位を満足する最良の変換、回転及びスケーリング用のパラメータを発見する。
公开号:JP2011513881A
申请号:JP2010550724
申请日:2009-02-23
公开日:2011-04-28
发明作者:ジー ブラスク，スティーヴン；マイネアー，キャサリーン
申请人:ハリス コーポレイションＨａｒｒｉｓ Ｃｏｒｐｏｒａｔｉｏｎ；
IPC主号:G06T1-00

专利说明:

[0001] 本発明は、雲状に分布するデータ点群（point cloud data）を記録又は登録することに関連し、特に、野外においてかなりの障害物の下にある（open and under significant occlusion）ターゲットの雲状に分布するデータ点群を記録又は登録することに関連する。]
背景技術

[0002] 画像処理システムにおいてしばしば生じる問題の1つは、ターゲットが他の対象物によって部分的に不鮮明になることであり、他の対象物はセンサがターゲットに適切に照射することや画像処理を妨げてしまう。例えば、光学系の画像処理システムの場合、木の葉やカモフラージュ用の網（camouflage netting）によってターゲットが遮られ、システムがターゲットを適切に画像処理する機能が制限されてしまう。さらに、ターゲットを遮る対象物はしばしば穴だらけのもの（porous）である。木の葉やカモフラージュ用の網は、そのような穴だらけの障害物の典型例であり、なぜならそれらはしばしば光を通す穴を含んでいるからである。]
[0003] 穴だらけのものの背後に隠れた対象物は、適切な技術を使用することにより検出及び認識できることが、知られている。遮るものを介したターゲットの瞬間観察（instantaneous view）は、ターゲットの表面の一部分しか含んでいないことが認められる。その部分的な領域は、遮るものの穴の領域を通して見えるターゲットの断片をなす。そのような穴の領域を通して見えるターゲットの断片は、画像処理センサの具体的な位置に依存して異なる。しかしながら、いくつもの様々な位置のセンサからのデータを収集することで、データ群を取得することができる。多くの場合、データの集合が分析され、ターゲットについての認識可能な画像が再構築される。通常、これは記録手順又は登録手順（registration process）を含み、その記録手順によって、様々な場所のセンサにより取得された特定のターゲットについての一連の画像フレームが収集され、そのシーケンスから1つの複合画像が構築される。]
[0004] 遮られている対象物の画像を再構築する場合において、3次元（3D）型のセンサシステムを利用することが知られている。3D型センサシステムの一例は、光検出レンジング（Light Detection And Ranging：LIDAR）システムである。LIDAR型3Dセンサシステムは、レーザ光による1つのパルスからの複数のレンジエコー（range echoes）を記録することで、画像フレームを生成する。したがって、LIDARデータの画像フレーム各々は、3次元における座標点の集まり（3D座標点群）を形成し、その3D座標点群は、センサ開口内の複数のレンジエコーに対応する。これらの点はしばしばボクセル（voxel）と言及され、3次元座標空間における格子の値を表す。3D画像処理に使用されるボクセルは、2D画像処理装置において使用されるピクセル（画素）に類似するものである。これらのフレームは、上述したようにターゲットの画像を再構築するように処理される。この場合において、3D座標点群に属する点の各々は、3D的なその状況における実際の表面を表す個々のx、y及びzの値を有することが理解されるべきである。]
発明が解決しようとする課題

[0005] 複数の視点やフレームにより部分的に見えるターゲットに関するLIDAR3Dデータ点群の集まりは、ターゲット判別、状況分析及び変化の検出等の目的に有用である。しかしながら、複数の視点やフレームを、全てのデータを合成した複合画像に組み立てるために、記録プロセスが必要になることが理解されるであろう。記録プロセスは、複数の場面（フレーム）の中から3D座標点群を並べ、3D座標点群により表現されるターゲットの観測可能な断片が、有用な画像とともに合成されるようにする。LIDARデータを用いて、遮られたターゲットの記録及び可視化に関する方法例は、特許文献1に記載されている。しかしながら、その文献で説明されている方法は、時間的に互いに近接したデータフレームを必要とし、したがって、LIDARを使用して非常に長い期間にわたって生じるターゲットの変化を検出するような場合には有用でない。]
課題を解決するための手段

[0006] 一実施例による方法は、
関心のあるターゲットに関する雲状に分布する3次元（3D）データ点群（雲状3Dデータ点群）の複数のフレームを記録する方法であって、
少なくとも第1のフレーム及び第2のフレームを取得するステップであって、前記第1及び第2のフレームの各々は、選択されたオブジェクトについて収集された雲状3Dデータ点群を含む、ステップと、
前記雲状3Dデータ点群を、前記第1フレーム及び前記第2のフレーム各々から2次元（2D）平面に射影することで、前記第1フレーム及び前記第2のフレーム各々の密度画像をそれぞれ作成するステップと、
前記第1のフレーム及び前記第2のフレームから取得した前記密度画像を利用して、少なくとも1つの変換ベクトルを決定するステップと、
前記少なくとも1つの変換ベクトルを利用して、XY平面及びZ平面の内の少なくとも1つにおいて、前記雲状3Dデータ点群について粗い記録を行うステップと
を有する方法である。]
図面の簡単な説明

[0007] 異なるセンサからのフレームが、なぜ記録を要するかを説明するための図。
記録プロセスが実行される雲状に分布するデータ点を含む一群のフレームの内の1つを示す図。
記録プロセスが実行される雲状に分布するデータ点を含む一群のフレームの内の1つを示す図。
記録プロセスが実行される雲状に分布するデータ点を含む一群のフレームの内の1つを示す図。
記録プロセスが実行される雲状に分布するデータ点を含む一群のフレームの内の1つを示す図。
記録プロセスが実行される雲状に分布するデータ点を含む一群のフレームの内の1つを示す図。
記録プロセスが実行される雲状に分布するデータ点を含む一群のフレームの内の1つを示す図。
本発明を説明するための記録プロセスのフローチャート。
図3のフローチャートにおける粗いXY記録ステップの詳細を示すフローチャート。
図3のフローチャートにおける粗いXZ記録ステップの詳細を示すフローチャート。
固有値メトリック群を使用する様子を示す図。
図3のフローチャートにおける細かい記録ステップの詳細を示すフローチャート。
フレームiについて、選択された雲状3Dデータ点群をXY平面に投影した様子を示すスクリーン画像群を示す図。
フレームjについて、選択された雲状3Dデータ点群をXY平面に投影した様子を示すスクリーン画像群を示す図。
フレームiについて取得されたXY密度画像を示すスクリーン画像群を示す図。
フレームjについて取得されたXY密度画像を示すスクリーン画像群を示す図。
フレームjについてメジアンフィルタリングを行う前のXY密度画像を示すスクリーン画像群を示す図。
フレームjについてメジアンフィルタリングを行った後のXY密度画像を示すスクリーン画像群を示す図。
フレームjについてソーベルフィルタリングを行う前のXY密度画像を示すスクリーン画像群を示す図。
フレームjについてソーベルフィルタリングを行った後のXY密度画像を示すスクリーン画像群を示す図。
フレームiについてフィルタリングされたXY密度画像、フレームjについてフィルタリングされたXY密度画像、2つのXY密度画像について相互相関を計算することで得られた相関曲面を示す複合的なスクリーン画像を示す図。
フレームiについて、選択された雲状3Dデータ点群をXY平面に投影した様子を示すスクリーン画像を示す図。
フレームjについて、選択された雲状3Dデータ点群をXY平面に投影した様子を示すスクリーン画像を示す図。]
[0008] 本発明は、関心のあるターゲットに関する2つ以上の雲状の3次元（3D）データ点群を記録又は登録する方法に関連する。本方法は、少なくとも第1のフレーム及び第2のフレームを取得することで始まり、第1及び第2のフレームの各々は、選択されたオブジェクトについて収集された雲状に分布する3Dデータ点群を含む。したがって、雲状に分布する3Dデータ点群を、第1及び第2のフレーム各々から2次元（2D）平面に投影することで、第1及び第2のフレーム各々に関する密度画像（density image）をそれぞれ取得することができる。第1のフレーム及び第2のフレームから取得した密度画像を利用して、1つ以上の変換ベクトル又は並進ベクトル（translation vector）が決定される。1つ以上の変換又は並進ベクトルを利用して、XY平面及びZ軸方向の内の1つ以上において、雲状に分布する3Dデータ点群について粗い記録（coarse registration）を行うために、1つ以上の変換又は並進ベクトルが使用される。本発明の一形態による本方法は、雲状に分布する3Dデータ点群の全体が占める空間又は体積より小さい空間（又は狭い体積）を有する雲状の3Dデータ点群の部分空間（sub−volume）を記録するステップを含んでもよい。]
[0009] 第1のフレーム及び第2のフレーム各々の密度画像は、XY密度画像のペア（組）を含み、そのXY密度画像は、第1及び第2のフレームにより取得された雲状の3Dデータ点群中のデータ点各々において、Z軸座標の値を0に設定することで得られる。第1のフレーム及び第2のフレーム各々の密度画像は、XZ密度画像のペア（組）を含み、そのXZ密度画像は、第1及び第2のフレームにより取得された雲状の3Dデータ点群中のデータ点各々において、Y軸座標の値を0に設定することで得られる。]
[0010] 以後、密度画像の各々はフィルタリングされ、フィルタリングされた密度画像になる。フィルタリングは、メジアン（median）フィルタリング、エッジ強調（edge enhancement）フィルタリング又は双方のタイプのフィルタリングを含む。第1のフレームから取得したフィルタリングされた密度画像と、第2のフレームから取得したフィルタリングされた密度画像との相互相関を計算することで、1つ以上の変換又は並進ベクトルが決定される。相互相関が実行されると、相互相関の出力マトリクスにおけるピークの位置に基づいて、1つ以上の変換又は並進ベクトルが決定される。]
[0011] 第1のフレーム及び第2のフレームによる雲状の3Dデータ点群の粗い記録は、有利なことに、複数の変換又は並進ベクトルを用いて、XY平面及びZ軸方向の双方に関して実行される。その後、本方法は、第1のフレーム及び第2のフレームによる雲状の3Dデータ点群について、細かい記録プロセス（fine registration process）を実行するステップが続く。]
[0012] 細かい記録プロセスはいくつものステップを有する。例えば、細かい記録プロセスは、第1及び第2の（3D）フレーム各々の中で2つ以上の部分空間を規定することから始まる。その後、雲状の3Dデータ点群について選択された配置を含む1つ以上の部分空間が、特定される。このステップは、部分空間各々に対する固有値群を計算することで実行される。その後、固有値を用いて、固有値メトリック群（set of eigen−metrics）が計算される。小さな塊のようなブロブ状の配置（blob−like arrangement）を有する3Dデータ点群を含む部分空間を特定するように、固有値メトリックが選択される。このプロセスは、フレーム1，2；1，3；1，4；2，3；2，4；2，5等のような隣接するシーン及び隣接していないシーンの双方について続けられ、ここで、連続する数字のフレームは隣接しており、連続してない数字のフレームは隣接していないものとする。]
[0013] 本方法は、部分空間の適格性を判別する際に、条件を満たすデータ点群（qualifying data points）を判別する。条件を満たすデータ点群は、データ点のペアを2つ以上含む。データ点のペア各々は、第1のフレーム内の第1のデータ点を含み、第1のデータ点は、第2のフレームにおける対応する第2のデータ点の位置に最も合致するものである。]
[0014] （上述した）全てのシーンのペアについて、条件を満たすデータ点群が特定されると、全てのフレームに関連する雲状の3Dデータ点群について、最適化ルーチンが同時に実行される。データセットにおける全てのフレーム及び全ての点に適用可能なグローバル変換マトリクス、グローバルスケール及びグローバルローテーション（global rotation）（変換、スケーリング及び回転等のパラメータ）を決定するために、最適化ルーチンが使用される。したがって、フレーム変換に対するローカルフレームではなく、グローバル変換が行われる。]
[0015] 細かい記録プロセスに使用可能な多くの最適化ルーチンが存在することが、理解されるべきである。あるものは、隣接するフレーム同士のみを処理し、シーンにおいてローカルなものである。これに対して、本発明は、有利なことに、グローバル変換を利用して、全てのフレームについて細かい記録を一度に行う。この点に関し、本発明は従来の方法と大きく異なる。従来の方法は、いくつものフレームに対する細かい記録プロセス又は平均化の際に、フレーム毎の記録を行っている。このような従来の方法は一般的に使用されているが、申し分のない結果を得るには適切でないことが分かった。]
[0016] 本発明により使用されるグローバル変換は、有利なことに、関心のあるフレームのペア各々について、全ての対応物（correspondence）を収集する。この場合において、本願において使用される「ペア」という用語は、フレーム1とフレーム2のような隣接しているフレームを単に示すだけではないことが、理解されるべきである。そうではなく、本願における「ペア」は、フレーム1，2；1，3；1，4；2，3；2，4；2，5等のようなものを含む概念である。これら全ての対応するペアが、細かい記録ステップにおけるグローバル最適化ルーチンにおいて同時に使用される。全てのフレーム同士の間の誤差（エラー）を最小化するパラメータが同時に出力され、フレームを変換する際に使用される。]
[0017] 雲状に分布する3次元データ点の複数のフレームを記録する発明方法を理解するために、先ず、そのようなデータの性質及び従来の取得方法を考察することが有用である。図1は、物理的な地域108の上空に或る距離を隔てて位置する2つの異なるセンサ102−i、102−jを示す。センサ102−i、102−jは、同じタイプであるが物理的には異なるセンサでもよいし、あるいは2つの異なる時間における1つの同じセンサを表現していてもよい。センサ102−i、102−jの各々は、物理的な領域108を表す雲状に分布した3次元データ点群による少なくとも1つのフレームを取得する。概して、「雲状に分布したデータ点群（point cloud data）」は、3次元空間における対象物を特定するディジタル化されたデータを示す。]
[0018] 本発明の説明の便宜上、物理的な場所108は、地表面上の地理的な場所として説明する。しかしながら、本願において説明される方法は、何らかの画像処理システムにおいて画像処理される任意のオブジェクト（対象）を表現する複数のフレームを含むシーケンスから、データを記録する場合にも適用可能であることが、当業者に理解されるであろう。例えば、そのような画像処理システムは、ロボット製造プロセス及び宇宙開発システムを含む。]
[0019] 雲状に分布する3Dデータ点群（雲状3Dデータ点群）を生成するのに使用可能な多種多様なセンサ、測定装置及び画像処理システムが存在することを、当業者は認めるであろう。本発明は、これらの様々な画像処理システムの内の何れかから取得された雲状3Dデータ点群を記録するために使用可能である。]
[0020] 雲状3Dデータ点群の1つ以上のフレームを生成する3D画像処理システムの一例は、従来のLIDAR画像処理システムである。概して、そのようなLIDARシステムは、高エネルギレーザ、光検出器（光ディテクタ）及びタイミング回路を使用して、ターゲットまでの距離を判定している。従来のLIDARシステムの場合、1つ以上のレーザパルスを使用して、シーン（場所）に照射する。各々のパルスは、ディテクタアレイとともに動作するタイミング回路にトリガを与える。概して、このシステムは、レーザからターゲットに至り、その後にディテクタアレイに戻って来る往復経路（ラウンドトリップ経路）を伝搬するパルスの画素各々について時間を測定する。ターゲットからの反射光がディテクタアレイにより検出され、そのラウンドトリップ時間が測定され、ターゲットの位置までの距離を判定する。計算される範囲ないし距離の情報は、ターゲットを構成する複数の点について得られるので、雲状に分布した3Dデータ点群を形成する。雲状に分布した3Dデータ点群は、対象物の3D形状を得るために使用される。]
[0021] 図1において、センサ102−i、102−jにより画像処理される物理的な空間108は、例えば車両のような1つ以上の対象物、目標物、オブジェクト又はターゲットを含む。しかしながら、センサ102−i、102−jとターゲットとの間の見通し線は、障害物（occluding materials）により部分的に遮られてしまうかもしれない。障害物は、関心のあるターゲットの雲状3Dデータ点群をセンサが取得することを遮る任意の種類のものを含む。LIDARシステムの場合、障害物は、樹木の葉のような自然界に存在するものや、カモフラージュ用の網のような人工のものを含む。]
[0022] 多くの場合、障害物106は、その性質上、穴が多い何らかのもの（porous）であることが認められる。したがって、センサ102−i、102−jは、障害物の穴の領域から見える（visible）ターゲットの断片を検出することができる。そのような穴の領域を通して見えるターゲットの断片は、センサ102−i、102−jの具体的な場所に依存して異なる。しかしながら、いくつもの異なるセンサの位置からのデータを収集することで、データの集まりを得ることができる。多くの場合、そのデータの集まりは分析され、認識可能なターゲットの画像を再構築する。]
[0023] 図2Aは、雲状に分布する3Dデータ点群200−iを含むフレームの一例を示し、これは図1のセンサ102−iにより取得されたものである。同様に、図2Bは、雲状に分布する3Dデータ点群200−jを含むフレームの一例を示し、これは図1のセンサ102−jにより取得されたものである。簡明化のため、図2A及び2Bにおける雲状3Dデータ点群のフレームは、それぞれ「フレームi」及び「フレームj」として言及される。雲状3Dデータ点群200−i、200−jの各々は、ある空間（体積）を占めるデータ点群の場所を規定し、それらの各々は、x、y、z軸における座標により3次元空間内で規定されることが、図2A及び2Bから分かる。センサ102−i、102−jが実行する測定により、データ点各々のx、y、z座標が規定される。]
[0024] 図1において、センサ102−i、102−jはそれぞれ異なる配置及び向きを有することがわかる。センサ102−i、102−jの配置及び向きは、センサの姿勢又はポーズとしてしばしば言及されることを、当業者は認めるであろう。例えば、センサ102−iは、「フレームiを構成する雲状3Dデータ点群200−iが取得された時点のポーズパラメータによって規定される姿勢を有する」、と言うことができる。]
[0025] 上記の説明により、フレームi、jにそれぞれ含まれる雲状3Dデータ点群200−i、200−jは、中心が異なるセンサの座標系に基づいていることが分かる。したがって、センサ102−i、102−jにより生成されるフレームi、jの雲状3Dデータ点群200は、異なる座標系に関して規定されている。これらの異なる座標系は、必要に応じて、空間的に回転及び並進（平行移動）させる必要があり、その後に、2つ以上のフレームからの雲状3Dデータ点群が共通する座標系において適切に表現されることを、当業者は認めるであろう。この場合において、本願により説明される記録プロセスの目的の1つは、2つ以上のフレームからの雲状3Dデータ点群を利用して、一連のフレーム中の各フレームについて必要なデータ点の相対的な回転及び並進を判定することであることが、理解されるべきである。]
[0026] フレームi及びフレームjにおける雲状3Dデータ点群の少なくとも一部が、共通の対象物（すなわち、同じ物理的な又は地理的な領域）に関して取得された場合にのみ、一連の雲状3Dデータ点群が記録されることにも留意を要する。したがって、フレームi及びjの少なくとも一部分は、一般に、共通する地理的領域（場所）からのデータを含む。例えば、各フレームの少なくとも約1／3の共通部分が、共通する地理的領域のデータを含んでいることが一般的に好ましい。さらに、フレームi及びjに含まれているデータは、時間的に互いに短時間の内に取得されたものであることを要しないことが、理解されるべきである。本願により説明される記録プロセスは、何週間も、何ヶ月もあるいは何年にもわたって取得されたフレームｉ及びjに含まれる雲状3Dデータ点群についても使用可能である。]
[0027] 図3を参照しながら、雲状3Dデータ点群の複数のフレームi、jを記録するプロセスの概要を説明する。本プロセスは、ステップ302から始まり、ステップ304に続く。ステップ302、304は、フレームi及びjを含む雲状3Dデータ点群200−i、200−jを取得することを含み、この場合において、フレームjは参照フレームとして指定されている。本ステップは、図1及び図2を参照しながら説明した方法を用いて実行される。各フレームについて雲状3Dデータ点群200−i、200−jを取得するのに使用される方法が具体的に何であるかは本発明に重要ではない。必要な全てのことは、結果のフレームが、空間内の複数の点各々の場所を規定するデータを含んでいること、及び各々の点はx、y、z軸の座標群によって規定されることである。]
[0028] 本プロセスはステップ400に続き、x、y平面に関し、フレームi、jに含まれているデータの粗い記録又は登録（coarse registration）を実行する。その後、フレームi、jのデータについての同様な粗い記録が、ステップ500においてx、z平面に関して実行される。粗い記録ステップについては後に詳細に説明する。しかしながら、本願において説明される粗い記録ステップは、有利なことに、基準フレーム（リファレンスフレーム）として指定される特定のフレームを選択することを含み、他の全てのフレームは基準フレームに対して整合することに、留意を要する。図3の場合、フレームiが基準フレームとして指定され、nフレーム全ての粗い記録を実行するために、jの値が反復されている。]
[0029] ステップ600において、記録されるフレームのシーケンスに属するnフレーム全てについて、粗い記録が完了したか否かの判断が行われる。完了していなかった場合、ステップ602においてjの値が増やされ（インクリメントされ）、プロセスはステップ304に戻り、次のフレームjの雲状データ点を取得する。その後、nフレーム全てについて記録が完了するまで、ステップ304、400、500、600、602が反復される。この段階において、プロセスはステップ700に進む。]
[0030] ステップ700では、ステップ400、500、600の粗い記録ステップにより粗く調整されたペア全てが、より正確な記録を行うために同時に処理される。ステップ700は、雲状3Dデータ点群のnフレーム全てについて、グローバル値RjTjを同時に計算することを含み、Rjは、フレームjの各々における全ての点をフレームiに整合させる（登録する又は記録する）ために必要な回転ベクトルであり、Tjは、フレームjにおける全ての点をフレームiに整合させる（登録する又は記録する）ために必要な並進ベクトルである。]
[0031] ステップ800は記録ステップの最終ステップである。ステップ700において計算された各フレームについてのRj及びTjの計算値を利用して、各フレームの雲状データ点群を共通の座標系に変換する。例えば、共通の座標系は、フレームiの座標系とすることができる。この段階において、一連のフレームに属する全てのフレームについての記録プロセスが完了する。例えば、収集期間（収集インターバル）の間に、センサは、3D測定値を含む25ないし40個の連続したフレームを収集する。これら全てのフレームが、図3に関して説明したプロセスにより整合させられる。プロセスはステップ900において終了し、一連のフレームから集約されたデータが表示可能になる。]
[0032] 図3のステップ400、500、700、800をさらに詳細に説明する。図4を参照するに、ステップ400における粗いx、yの記録は、ステップ402から始まる複数のステップを含む。ステップ402において、フレームi、jの各々が水平にスライスされ（すなわち、図2のx、y軸により規定される平面に水平にスライスされ）、雲状3Dデータ点群200−i、200−jをなす部分の空間全体が選択される。この様子は図2C、2Dに示されており、フレームi、jにおける部分空間をなす平面201、202を示す。有利なことに、関心のあるターゲットを含んでいると考えられ、かつ関心のない無関係なデータを含まない空間として、部分空間203が選択される。]
[0033] 本発明の一実施例において、選択されるフレームの部分空間は、ある場所に対応する雲状3Dデータ点群を含み、その場所は、地表面より僅かに上にあり、地面から所定の高度又は高さに及んでいるものである。例えば、地面からz＝0．5メートルないし地面からz＝6．5メートルの範囲内にある部分空間は、地上のほとんどの種類の車両その他の対象物を包含するのに通常適している。しかしながら、本発明はこのような場合に限定されないことが理解されるべきである。別の状況において、地面に対して高い場所から始まる部分空間を選択し、シーン内の高い対象物（例えば木の幹）のみに基づいて、記録が実行されるようにすることが望ましい場合もある。木々の影により遮られている対象物の場合、地面から、低い木の枝（tree limbs）より若干低いところに伸びる部分空間を選択することが望ましい。]
[0034] ステップ404において、雲状3Dデータ点群200−i、200−jをなす様々なデータ点が、雲状データ点群における各自の位置により、各自のx、y平面に射影又は投影される。言い換えれば、各フレーム内のデータ点のx及びy座標の値は同じであるが、各データ点のz座標の値は0に設定される。ステップ404の結果により、雲状3Dデータ点群をなす各フレームi、jは、x、y平面における2次元フレーム（XYフレーム）に変換される。図8Aは、フレームiについて、選択された雲状3Dデータ点群をXY平面に射影した様子を示す。図8Bは、フレームjについて、選択された雲状3Dデータ点群をXY平面に射影した様子を示す。この場合において、選択された雲状3Dデータ点群は、何れの場合も、ステップ402において選択された雲状3Dデータ点群になることが理解されるであろう。]
[0035] ステップ405では、フレームi、jについて雲状3Dデータ点群をXY平面に射影したものを利用して、XY密度画像を生成する。一実施例において、XY密度画像は、5ボクセルサイズ×5ボクセルサイズのウィンドウを用いることで生成される。1ボクセルは、シーンデータの1立方体の部分である。本願において、「ボクセルサイズ」という用語は、1つの立方体のボクセルの1辺の長さを示す。例えば、1ボクセルは、LIDARセンサの分解能に基づいて、（0．2m）3のサイズを有する。この場合、ボクセルサイズは0．2mとなり、フィルタウィンドウは、1．0m×1．0mの大きさを有する。このウィンドウを利用して、空間データの2DXY射影（Z＝0）を処理する。ボクセルサイズ×ボクセル数（voxelsize＊numvoxels）（マイナス何らかのフィルタエッジの影響）は、密度画像の幅に等しい。したがって、ボクセル数という用語は、密度画像の幅の大きさに対応する方向に整列するボクセル数を示す。一部のボクセル及びエッジの影響が排除された後、密度画像の幅は2DXY射影画像の幅に非常に近くなることに、留意を要する。]
[0036] 上述したウィンドウは2D射影を考慮せず、ウィンドウにおけるヒット数（密度）は、そのウィンドウ位置における値として使用される。ボクセルサイズは、データの処理解像度に基づいており、メートルで表現される。本願において説明する密度画像を生成することで、希薄な（sparse）ボクセルについて小さな「ウェイト」を与えることに（すなわち、これらのボクセルはほとんど「ヒット」していないことに）、留意を要する。そのような領域は、粗い記録ステップにおいて重要ではなく、まばらな木の葉（茂み、低く横たわっている木の幹等）等を含んでいるかもしれない。また、それらは岩や木の幹と同程度に時間に関して不変的ではない。]
[0037] 上記の手順を利用することで、フレームiについてXY密度画像が取得され、フレームjについてXY密度画像が取得される。図9Aは、フレームiについて、雲状3Dデータ点群のXY射影から取得されたXY密度画像を示す。図9Bは、フレームjについて、雲状3Dデータ点群のXY射影から取得されたXY密度画像を示す。]
[0038] 上記のXY密度画像の目的は、以後に適用されるフィルタリングプロセスが、記録される2D形状の端（縁、周囲、輪郭、エッジ）を発見できるようにすることである。密度画像をフィルタリングすることを含む本願により説明される方法は、ある画像に現れる何らかのタイプのオブジェクト（対象物）を記録するための好ましい方法であることに、留意を要する。特に、本プロセスは固有値メトリック法（eigenmetric method）に対して演算負担が少なく適用できるので、本プロセスは野外に置かれている対象物（すなわち、遮られていない、あるいは僅かにしか遮られていない対象物）に対して良好に機能する。かなり遮られている対象物の場合、各フレーム内には限られたデータ点しか存在しないので、かなり遮られている対象物にはこの方法が良好に機能しないことを、当業者は予想するであろう。しかしながら、本記録方法は、木々の影になっている対象物についても予想外に良好に機能することを確認できた。3D画像によるデータサンプルのスライスが注意深く選択されるならば、相関を計算するのに十分であり、かつ上記の「不完全な」フレームについての粗い記録を完了するのに十分な形状データを利用できる。この場合において、データ点のスライスは、地面から低木の枝より僅かに低い高さに至るまでの間のデータ点しか含まないように、選択されることがそのような場合には好ましい。]
[0039] ステップ406に本プロセスは続き、フレームiについてのXY密度画像及びフレームjについてのXY密度画像から、フィルタリングされたXY密度画像i及びフィルタリングされたXY密度画像jをそれぞれ作成する。この場合において、ステップ406は、（1）XY密度画像i、jについてメジアンフィルタリング（median filtering）を実行し、（2）メジアンフィルタリングされたXY密度画像i、jについてソーベルエッジフィルタリング（Sobel edge filtering）を実行するステップを含む。これらのフィルタリングのステップについて以下において詳細に説明する。]
[0040] メジアンフィルタリングは、主に、XY密度画像i、jにおけるノイズを削減するために実行される。メジアンフィルタは当該技術分野において知られている。したがって、プロセスを詳細には説明しない。概して、明示案フィルタリングは、高さ及び幅の方向におけるあるピクセル数に相当するフィルタマスクを選択することを含む。マスクの具体的なサイズは、特定のアプリケーションに依存して異なる。目下の例の場合、高さ方向に5ピクセル及び幅方向に5ピクセルのサイズを有するフィルタマスクが、適切な結果をもたらすことが見出された。しかしながら、本発明はこの例に限定されない。実際には、マスクは画像の中でスライドされ、マスクに含まれている中心ピクセルが、隣接するピクセルと比較して同様な値を有するか否かが検査される。同様な値を有していなかった場合、そのピクセルはノイズにより誤りを含んでいる（劣化している）ことの指標になることが多い。したがって、メジアンフィルタは、中心のピクセルの値を、マスクの中の残りのピクセルの中央値（メジアン）で置換する。メジアンの算出は、先ずマスクの中のピクセル値全てを数値の順に並べ、考察するピクセルを、中央のピクセル値で置換することで行われる。図10Aは、フレームjについてメジアンフィルタリングを行う前のXY密度画像を示す。図10Bは、フレームjについてメジアンフィルタリングを行った後のXY密度画像を示す。]
[0041] フィルタリングされた密度画像を準備する際、エッジフィルタリングが行われる。画像処理の技術分野における当業者は、2つの画像を整合させる場合、画像に含まれている対象物のエッジ（輪郭）を特定することが有用であることを認めるであろう。画像を形成する対象物のエッジを検出することで、画像に含まれる総データ量をかなり削減できる。エッジ検出は、画像の重要な構造的特徴を保ち、画像を整合させる際に一般的には有用でない情報を排除する。したがって、メジアンフィルタリングを行った後に、XY密度画像についてエッジフィルタリングを行うことは有利である。]
[0042] 本願において使用されているように、「エッジ」という用語は、強いコントラストが存在する2次元画像内の領域を示す。そのような領域の場合、隣接するピクセル同士の間で急激に強度が変化しているのが通常的である。なお、エッジ検出を実行する多種多様な方法が存在するが、それら全ての方法は、本発明の範囲内に含まれるように意図されていることが、理解されるべきである。本発明に使用可能なエッジフィルタリングは、現在知られている任意の方法又は将来発見される任意の方法を含むことができ、画像内のエッジを検出又は強調するために使用可能である。]
[0043] 好適実施例によれば、本発明によるエッジフィルタリングは、従来のソーベルフィルタを用いて実行可能である。ソーベルフィルタリング法の場合、画像の2D空間の勾配の測定値（2D spatial gradient measurement）を判定するために、ソーベルオペレータ（ソーベル演算子）が使用される。従来のソーベルフィルタリング処理方法については既知である。したがって、ソーベルフィルタリング法自体について詳細には説明しない。概して、x方向における勾配を判定するため、3ピクセルの高さ及び3ピクセルの幅の第1の畳み込みマスク（convolution mask）が使用される。y方向における勾配を判定するため、3ピクセルの高さ及び3ピクセルの幅の第2の畳み込みマスクが使用される。この場合において、第1及び第2の畳み込みマスクの各々は、実際のXY密度画像よりも十分に小さいことが、理解されるべきである。マスクはそれぞれ画像の中でスライドされ、ソーベル演算子により、3×3のピクセルグループの1つが一度に操作される。第1の畳み込みマスクは、第1の方向におけるエッジを強調する一方、第2の畳み込みマスクは、第1の方向と交差する第2の方向におけるエッジを強調する。本願において使用されているように、「強調」という用語は、雲状に分布する点群のエッジが、より明確に規定されるように、画像又はデータを強調すること一切を示す。このプロセスの結果は、x軸及びy軸双方に沿う方向において強調されたエッジとなる。図11Aは、メジアンフィルタリングの後に、ソーベルフィルタリングを行う前のXY密度画像を示す。図11Bは、ソーベルフィルタリング後のXY密度画像を示す。フィルタリングされたXY密度画像は図11Bに示されており、これは、メジアンフィルタリングの効果を含むことに加えて、ソーベルフィルタリングによるエッジ強調の効果も含んでいる。]
[0044] ステップ408において、XY並進エラー（又はXY変換エラー）が判定される。XY並進エラーは、フィルタリングされたXY密度画像iにより表現される画像データと、フィルタリングされたXY密度画像jにより表現される画像データとの間のx、y平面におけるシフト、偏移、ずれ又はオフセットである。XY並進エラーは、あるベクトルにより規定することができ、そのベクトルは、2つのフィルタリングされたXY密度画像i、jの間のシフト又はオフセットの方向及び距離を特定する。XY並進エラーを判定する方法の1つは、フィルタリングされたXY密度画像i、jの相互相関を計算することである。2つの画像の相互相関は、2つの画像の間の類似性を判定するために使用可能な標準的な方法であり、これは当該技術分野において知られている。2つの画像が少なくともいくつかの共通する対象物を含んでいた場合、相互相関処理を行うと、実際のXY並進エラーに対応する位置において、相関値のピークが得られるのが一般的である。]
[0045] 連続的なフレーム同士の場合、回転による変化はほとんどないことに、特に留意を要する。言い換えれば、画像処理する場面（シーン）について、画像処理装置の観点からは、回転の変化はほとんどない。そのような場合、2つの画像に含まれている場面同士の間に関し、回転について不変でない相関法を使用することが可能である。例えば、この目的に対して、従来の規格化された相関法を使用することができる。]
[0046] さらに、規格化された相関（値）は、一般に、2つ又は3つの自由度の回転変化にのみ使用可能であることが、理解されるべきである。かなり異なる時間に異なる方向から取得されたフレームの場合（例えば、6ヶ月隔たっている場合）、2D射影の場合（野外の対象物に好ましいモードの場合）及び3D空間の場合（木の陰になって遮られている対象物に好ましいモードの場合）、そのような規格化された相関プロセスを用いると、相当大きな回転エラーが生じる。この問題は、支持データ（サポートデータ）を収集し、データの向きを調整できるようにすることで解決できる。しかしながら、そのようなデータが利用可能でない場合や、単に使用されていない場合、回転に関して不変な相関プロセスを使用することが望ましい。回転に不変な相関プロセス自体については当該技術分野において既知である。]
[0047] 本発明の場合、フィルタリングされた密度画像i、jについて、規格化された相互相関を計算する。この場合において、相互相関の計算結果を曲面状にプロットして表示すると便利である。フレームi、jについてのXYフィルタリング密度画像が最も相関する場所において、相互相関曲面のピークが生じる。重要なことに、相関ピークの位置は、フレームi、jの間のx、y平面におけるシフトを示す。求める実際のXY並進エラーベクトルは、そのピーク位置から容易に判定できる。簡単に言えば、フレームの中心から算出された2つのフレーム間のデルタx（x方向のずれ）及びデルタy（y方向のずれ）である。調整は、基準フレームを固定しつつ行われる。2つのフレームしかなかった場合、いずれが基準になってもよい。一連のフレームの場合（例えば、木々の陰に位置している対象物について収集された場合）、中央のフレームが、基準フレームとして最良に機能する。]
[0048] ステップ408に関して説明される相関プロセスは、フィルタリングされたXY密度画像i、jについて実行される規格化相互相関（Normalized Cross Correlation：NCC）プロセスを含んでもよい。2次元画像を記録するためにNCCを使用すること自体は、当該技術分野において知られている。したがって、NCCプロセス自体について詳細には説明しない。概して、2つの画像i、jの相互相関は、次のような積として定義される：



ここで、piは、フィルタリングされたXY密度画像iにおいて、関心のある領域wiの中で変化するピクセルインデックスであり、pjは、フィルタリングされたXY密度画像jにおいて、関心のある領域wjの中で変化するピクセルインデックスである。]
[0049] として示される相互相関積は、相互相関の用途に応じて多種多様な関数により規定できる。しかしながら、典型的な積の定義の一例は、次のとおりである：



上記の積の定義は、2つの異なる画像に含まれている関心のある2つの領域が、どの程度類似するかを示す指標をもたらすことが、当業者に認められるであろう。この場合において、最良の相関が得られた場合、相互相関値はピークを示す。当然ではあるが、本発明はこれに限定されず、他の如何なるNCCプロセスが使用されてもよい。ただし、そのNCCプロセスは、XY密度画像i及びXY密度画像jの間の並進エラーを特定する計算結果をもたらすものであるとする。]
[0050] 図12は、フレームiから取得されたフィルタリングされた密度画像と、フレームjから取得されたフィルタリングされた密度画像と、それらのフィルタリングされた密度画像について規格化された相互相関を計算することで得られた相関曲面とを示す複合的なスクリーン画像群を示す。図示されているように、相関曲面は相関ピークを含んでいる。]
[0051] 本発明の代替実施例では、NCCプロセスの代わりに、異なる方法を用いてXY並進エラーを判定する。特に、NCCは、回転に不変な類似メトリック（similarity metric）により置き換えられる。当業者に理解されるように、適切な如何なる類似メトリックがこの目的に使用されてもよい。ただし、類似メトリックは、回転に対して不変であり、あるいはNCCプロセスの場合と比較して、回転変化に対して、より少ない影響しか受けないものとする。フレームi、jが得られた場合、センサ102−iの姿勢（ポーズ）がセンサ102−jに対して回転していたような状況において、回転に対して不変な類似メトリック（回転不変類似メトリック）は特に有利である。]
[0052] ステップ408のXY並進エラーを判定するのに使用される具体的な方法によらず、その結果は、x、y平面における何らかの並進エラーベクトルとなり、フィルタリングされたXY密度画像i及びフィルタリングされたXY密度画像jの間のXY並進エラーを規定する。この並進エラーベクトルが決定されると、本プロセスはステップ410に続く。ステップ410では、並進エラーベクトルを用いて、フレームi、jにおけるデータ点の位置を粗く調整し、データ点が互いに近似的に整合するようにする、少なくともx、y平面におけるそれらの位置に関して整合するようにする。本プロセスはステップ500に続き、x、y平面における粗い調整が完了した後のフレームi、jが、z軸における粗い調整のために使用される。]
[0053] 図5のフローチャートを参照するに、ステップ500の粗いz座標の記録は、ステップ502、504、506、508、510という複数のステップを含む。これらのステップは、概して、図4のステップ402、404、406、408、410と類似しているが、図5の場合、粗い記録がx、y平面ではなく、z軸について実行される点が主に異なる。]
[0054] 図5を参照するに、ステップ500において、z軸方向における粗い調整がステップ502から始まる。ステップ502の場合、フレームi、jの各々は垂直にスライスされ（すなわち、x軸及びz軸により規定される平面に平行にスライスされ）、雲状3Dデータ点群200−i、200−jを構成する部分の空間全体が選択される。この様子が図2E、2Fに示されており、フレームi、jにおける部分空間205を形成する平面203、204が示されている。有利なことに、部分空間205は、関心のあるターゲットを含むと思われる空間として選択される。本発明の一実施例において、選択されるフレームi、jの部分空間205は、ある複数の位置に対応する雲状3Dデータ点群を含み、その複数の位置は、図2のx、z軸により規定される平面の何れかの側から所定の距離だけ離れている。例えば、y＝−3メートルないしy＝＋3メートルの範囲内の部分空間は、地上の車両その他の対象物を検出するのに便利な部分空間である。しかしながら、本発明はそのような場合に限定されない。別の状況の場合、x、z軸により規定される平面から遠くまで及ぶ又は近くまでしか及ばない部分空間を選択することが望ましい。]
[0055] ステップ504に続く本方法では、雲状3Dデータ点群200−i、200−jをなす様々なデータ点が、雲状データ点群における各自の位置により、x、z平面に射影又は投影される。言い換えれば、データ点のx及びz座標の値は同じであるが、各データ点のy座標の値は0に設定される。ステップ504の結果により、雲状3Dデータ点群をなす各フレームi、jは、x、z平面における2次元フレーム（XZフレーム）に変換される。図13Aは、フレームiについて、選択された雲状3Dデータ点群をx、z平面に射影した様子を示す。図13Bは、フレームjについて、選択された雲状3Dデータ点群をx、z平面に射影した様子を示す。]
[0056] ステップ505では、フレームi、jについて雲状3Dデータ点群をXZ平面に射影したものを利用して、XZ密度画像を生成する。XZ密度画像は、XY密度画像に関して説明したものと同様な方法で生成されるが、Yの値が0に設定される点が異なる。このようにして、フレームiについてXZ密度画像が得られ、フレームjについてXZ密度画像が得られる。]
[0057] ステップ506に本プロセスは続き、フィルタリングされたXZ密度画像i及びフィルタリングされたXZ密度画像jを作成する。これらのフィルタリングされたXZ画像は、フレームiに対するXZ密度画像及びフレームjに対するXZ密度画像からそれぞれ取得される。ステップ506においてフィルタリングされたXZ密度画像i、jを作成する際、実際には少なくとも2つのステップが含まれる。概して、ステップ506は、（1）XZ密度画像i、jについてメジアンフィルタリングを実行し、（2）メジアンフィルタリングされたXZ密度画像i、jについてソーベルエッジフィルタリングを実行するステップを含む。これらの中間的なステップは、図4を参照しながら詳細に説明されている。したがって、ここでは説明を繰り返さない。]
[0058] ステップ508において、Z並進エラー（又はZ変換エラー）の粗い判定がなされる。Z並進エラーは、フィルタリングされたXZ密度画像iにより表現される画像データと、フィルタリングされたXZ密度画像jにより表現される画像データとの間に存在するz軸方向におけるシフト、偏移、ずれ又はオフセットである。Z並進エラーは、あるベクトルにより規定することができ、そのベクトルは、2つのフィルタリングされたXZ密度画像i、jの間のシフト又はオフセットの方向を特定する。Z並進エラーを判定する方法の1つは、ステップ408に関して既に説明したのと同様に、フィルタリングされたXZ密度画像i、jについて、NCC処理を実行することである。あるいは、Z並進エラーを判定するNCC法を使用する代わりに、他のタイプの類似メトリックが使用されてもよい。この場合において、フレームi、jが得られた場合、センサ102−iのポーズがセンサ102−jに対して回転していたような状況において、回転に対して不変な類似メトリックは特に有利であることが認められるであろう。]
[0059] ステップ508のZ並進エラーを判定するのに使用される具体的な方法によらず、その結果は、フィルタリングされたXZ密度画像i及びフィルタリングされたXZ密度画像jの間のようなZ方向におけるシフトとして、Z並進エラーを規定するベクトルになる。この並進エラーベクトルが決定されると、本プロセスはステップ510に続く。ステップ510では、Z並進エラーベクトルを用いて、フレームi、jにおけるデータ点の位置を粗く調整し、データ点が、x、z平面における各自の位置に関して互いに近似的に整合するようにする。その後、本プロセスはステップ600に続く（図3参照）。]
[0060] 雲状3Dデータ点群を構成するフレームi、jについての上述のプロセスは、一群の雲状3Dフレーム群（フレームセット）を構成する複数のフレームペアについて反復される。本プロセスは、隣接するフレーム1、2から始まり、フレーム1は基準フレームとして使用され（i＝1）、他のフレームは基準フレームに合わせて揃えられる。しかしながら、フレームセット内の中央のフレームを基準フレームとして使用し、粗い記録プロセスを開始することが有利である。例えば、25個のフレームがあった場合、フレーム13が基準フレームとして使用可能である（i＝13）。粗い記録ステップが、フレーム14をフレーム13に合わせるために使用され、フレーム15は、粗く合わせられたフレーム14に合わせられ、以下同様である。さらに、反対方向において、フレーム12はフレーム13に合わせられ、フレーム11は、粗く合わせられたフレーム12に合わせられ、以下同様である。図3のステップ602におけるフレームjに関する反復は、もはやjの単調増加ではないので、図3のフローチャーに些細な変更が必要になることを、当業者は認めるであろう。]
[0061] 図3を再び参照するに、ステップ400、500、600の粗い記録ステップに続いて、ステップ700において細かい記録プロセスが実行される。特に、上記の粗い記録ステップが完了した後に、雲状3Dデータフレームi、jについて、細かい記録（高精度な記録）を実行するのに使用可能な様々な従来の方法が存在することを、当業者は認めるであろう。それらの任意の細かい記録ステップが、本発明に使用可能である。例えば、グローバル最適化ルーチンを含む簡易な反復法が使用可能である。そのような方法は、粗い記録が完了した後に、フレームi及びフレームjにおけるデータ点の位置関係を最も良く記述（説明）するx、y、z軸方向の並進法（変換法）を見出すことを含む。この場合において、最適ルーチンは、フレームi、jにおける点同士の対応関係を記述（説明）するデータ点の様々な位置変換を見出すステップと、その後に、位置変換の特定の反復において、最も近い点を見出すステップとを反復する。当該技術分野において既知の様々な数学的方法が、この場合に適用可能である。例えば、この場合に適用可能な数学的方法の1つが、非特許文献1に記載されており、その開示内容は本願のリファレンスに組み入れられる。]
[0062] 図7を参照すると、細かい記録ステップ700は、ステップ710から始まる複数のステップを含んでいる。ステップ710において、フレームi及びフレームjの各々は、複数の部分空間に分割される。細かい記録プロセスに備えて、フレームi及びフレームjの空間全体と比較して、各自がかなり小さな空間を占める部分空間が選択される。例えば、一実施例において、フレームi及びフレームjの各々を構成する空間は、16個の部分空間に分割されてもよい。シーン（場面）の中に現れる選択されたオブジェクトについて予想されるサイズ（大きさ）に基づいて、部分空間の具体的なサイズが選択される。]
[0063] ステップ720に続く本プロセスは、固有値解析を実行し、ステップ710において規定された部分空間各々について、一群の固有値λ1、λ2、λ3を決定する。固有値分析を利用して、対称的なマトリクス（行列）により表現されるデータ構造のサマリ（概要、特徴）をもたらすことは、当該技術分野において既知である。この場合において、一群の固有値各々を計算するのに使用される対称的なマトリクスは、部分空間各々に含まれる雲状に分布するデータ点群（雲状データ点群）であるように選択される。部分空間各々における雲状データ点の各々は、x、y、zの値により指定される。したがって、データのまわりに楕円（楕円体）を描くことができ、その楕円は、3つの値（すなわち、λ1、λ2、λ3）により規定することができる。第1の固有値は常に最大であり、第3の固有値は常に最小であるとする。この段階において、構造又は形状を予想することができる。例えば、オブジェクトは、トラック車両かもしれないし、木の幹かもしれない。図6に示す数式を使用して、及びどの固有値が最大及び最小であるかの情報に基づいて、固有値メトリックを計算することができる。]
[0064] 固有値を計算する方法及び技法は、当該技術分野において既知である。したがって、その方法について詳細には説明しない。一般に、部分空間内のデータは、XYZ座標点のリストから構成される。最大であるλ1とともに、各固有値をもたらすデータについて、固有値分解（eigenvalue decomposition）が実行される。目下の例のフレームは連続的に収集されているので、隣接するフレームの方向は類似している。したがって、固有値λ1、λ2、λ3の各々は、0及び1．0の間の値をとる。]
[0065] 図6のテーブル（表）を利用して、固有マトリクスが求められ、部分空間内の雲状に分布するデータの構造又は分布の形状を判別する。雲状3Dデータ点群の各フレームについて既に実行されている粗い調整は、各フレーム中対応する部分空間が、シーンに含まれている対応する構造又はオブジェクトに関するデータ点を含んでいることを期待できる程度に充分である。]
[0066] 上述したように、これらの固有値は、対称的なマトリクスにより表現されるデータ構造を特徴付ける又は要約するのに特に有用である。本発明の場合、固有値λ1、λ2、λ3は、一連のメトリックを計算するのに使用され、これらのメトリックは、部分空間内の雲状3Dデータ点群により形成される形状の指標を与えるのに有用である。例えば、図6のテーブル（表）は3つのメトリックを規定し、これらが計算され、線状、平面状、塊状（blob−like）のオブジェクトであることを示すために、メトリックがどのように使用されるかを示す。塊状のデータ点群は、3次元的なボール（球）や、不定形状を有する塊であると考えられる。したがって、ここで参照されている塊状のデータ点群は、直線、曲線又は平面を構成するデータ点群を含まない。]
[0067] 図6を参照するに、固有値λ1、λ2、λ3を利用して計算されるメトリックM1、M2、M3は、次のように計算される：



M1、M2、M3の値が全て1．0に近似的に等しい場合、これは、その部分空間が、平面や直線状のデータ点群ではなく、塊状のデータ点群を含んでいることを示す。例えば、特定の部分空間についてのM1、M2、M3の値が全て0．7より大きかった場合、その部分空間は塊状のデータ点群の構造を有すると結論づけることができる。さらに、本発明はこのような例に限定されないことを、当業者は認めるであろう。さらに、本発明は図示の特定のメトリックに限定されないことも、当業者は直ちに認めるであろう。むしろそうではなく、適切な任意のメトリックが使用可能である。ただし、それらのメトリックは、塊状のデータ点群が、直線、曲線、平面を規定するデータ点群と区別できるものとする。]
[0068] ステップ730において、固有値分析の結果及び図6の表を利用して、細かい記録プロセスに最も有利に使用可能なフレームi、jの部分空間（条件を満たす部分空間）を特定する。ここで使用されているように、「条件を満たす部分空間（qualifying sub−volume）」は、ステップ710において規定された部分空間のうち、固有値メトリックが塊状のデータ点群の構造を含むことを示している部分空間をいう。十分な数のデータ又は内容を含んでいるように、条件を満たす部分空間をさらに限定することが、有用である。例えば、条件を満たす部分空間は、少なくとも所定数のデータ点を含んでいるように限定することができる。一連のフレームにより表現される隣接する及び隣接していないシーンの双方を構成する複数のシーンペアについて、ステップ730のプロセスが実行される。例えば、シーンペアは、フレーム1，2；1，3；1，4；2，3；2，4；2，5等を含むが、この場合において、連続的な番号のフレームは隣接しており、連続的でない（不連続な）番号のフレームは隣接していないものとする。]
[0069] 記録プロセスに最も有用な条件を満たす部分空間が選択されると、本プロセスはステップ740に続く。より具体的には、ステップ740において、本プロセスは、条件を満たす部分空間に含まれているデータ群中のシーンペア各々について、データ点の対応するペアを特定する。このステップは、あるフレーム（例えば、フレームj）の「条件を満たす部分空間」におけるデータ点を見出すことで行われ、そのデータ点は、他のフレーム（例えば、フレームi）の「条件を満たす部分空間」におけるデータ点の位置又は配置に最も良く合致するものである。条件を満たす部分空間における未処理データ点を利用して、フレームペア同士の間の対応関係を見出す。フレームペア同士の間の点の対応関係は、K−Dツリーサーチ法（K−D tree search method）を用いて見出すことができる。当該技術分野において既知のこの方法は、最近接探索法（nearest neighbor search method）と言及されることもある。]
[0070] ステップ750において、フレーム全てに関連する雲状3Dデータ点群について、最適化ルーチンが同時に実行される。最適化ルーチンは、データ群中の全ての点及び全てのフレームに適用可能なグローバルローテーション、スケール及び変換マトリクス（変換、スケーリング及び回転等のパラメータ）を決定するために使用される。すなわち、ローカルなフレーム毎の変換ではなく、グローバルな変換が行われる。より具体的には、最適化ルーチンは、各フレームj各々について、回転及び並進ベクトルRiTiを見出すために使用され、回転及び並進ベクトルは、ステップ740において指定されたデータ点の対応するペア全てについて、エラーを同時に最小化するものである。フレームiに含まれる全ての点に整合するように、各フレームj内の全ての点について、回転及び並進ベクトルが使用される。当該技術分野において既知であり、本願に仕様う可能ないくつもの最適化ルーチンが存在する。例えば、最適化ルーチンは、同時摂動確率近似（simultaneous perturbation stochastic approximation：SPSA）を含んでもよい。使用可能な他の最適化方法は、ネルダーメッドシンプレックス法（Nelder Mead Simplex method）、最小二乗適合法（Least Squares Fit method）及び準ニュートン法（Quasi Newton method）を含む。さらに、SPSA法は、上記の最適化を実行するのに好ましい。これらの最適化法の各々は、当該技術分野において既知であり、したがって詳細には説明しない。]
[0071] 本発明はデータ処理システム又はコンピュータプログラム（又はプログラム製品）として実現されてもよいことを、当業者はさらに認めるであろう。したがって、本発明は、完全にハードウェアとして実現されてもよいし、完全にソフトウェアとして実現されてもよし、あるいはソフトウェア及びハードウェアの組み合わせとして実現されてもよい。本発明は、コンピュータ読取可能案プログラムコードが記憶されているコンピュータ読取可能な記憶媒体におけるコンピュータプログラム又はプログラム製品の形態をとってもよい。適切な如何なるコンピュータ読取可能な媒体が使用されてもよく、例えば、RAM、ディスクドライバ、CD−ROM、ハードディスク、磁気ストレージ装置でもよいし、及び／又は他の任意の形式のプログラムバルクストレージでもよい。]
実施例

[0072] 本発明を担うプログラムコードは、ジャバ（Java）（登録商標）、C＋＋又は他のオブジェクト指向プログラミング言語により書かれたものでもよい。しかしながら、コンピュータプログラムコードは、従来の処理プログラム言語（例えば、Cプログラミング言語）により書かれたものでもよい。コンピュータプログラムコードは、目視指向（visually oriented）プログラミング言語（例えば、VisualBasic）により書かれたものでもよい。]
[0073] 米国特許出願公開第2005／0243323号明細書]
先行技術

[0074] J.Williams and M.Bennamoun eititled “Simultaneous Registration of Multiple Point Sets Using Orthonormal Matricies”Proc.,IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP’00)]

权利要求:

請求項1
関心のあるターゲットに関する雲状に分布する3次元（3D）データ点群（雲状3Dデータ点群）の複数のフレームを記録する方法であって、少なくとも第1のフレーム及び第2のフレームを取得するステップであって、前記第1及び第2のフレームの各々は、選択されたオブジェクトについて収集された雲状3Dデータ点群を含む、ステップと、前記雲状3Dデータ点群を、前記第1フレーム及び前記第2のフレーム各々から2次元（2D）平面に射影することで、前記第1フレーム及び前記第2のフレーム各々の密度画像をそれぞれ作成するステップと、前記第1のフレーム及び前記第2のフレームから取得した前記密度画像を利用して、少なくとも1つの変換ベクトルを決定するステップと、前記少なくとも1つの変換ベクトルを利用して、XY平面及びZ平面の内の少なくとも1つにおいて、前記雲状3Dデータ点群について粗い記録を行うステップとを有する方法。
請求項2
前記雲状3Dデータ点群の全体が占める空間より小さい空間を有する前記雲状3Dデータ点群の部分空間を、各フレームから排他的に選択するステップをさらに有する、請求項1記載の方法。
請求項3
前記第1及び第2のフレームにより取得された雲状3Dデータ点群に属するデータ点各々に対して、z軸座標の値を0に設定することで、前記第1のフレーム及び前記第2のフレーム各々について、XY密度画像となる密度画像を選択するステップをさらに有する、請求項1記載の方法。
請求項4
前記第1及び第2のフレームにより取得された雲状3Dデータ点群に属するデータ点各々に対して、y軸座標の値を0に設定することで、前記第1のフレーム及び前記第2のフレーム各々について、XZ密度画像となる密度画像を選択するステップをさらに有する、請求項1記載の方法。
請求項5
前記変換ベクトルを決定する前に、前記密度画像の各々をフィルタリングし、前記第1のフレーム及び前記第2のフレームの各々についてフィルタリングされた密度画像を取得するステップをさらに有する、請求項1記載の方法。
請求項6
前記少なくとも1つの変換ベクトルを決定する前記ステップにおいて、前記第1のフレームから取得した前記フィルタリングされた密度画像と、前記第2のフレームから取得した前記フィルタリングされた密度画像との相互相関を計算する、請求項5記載の方法。
請求項7
前記第1のフレームからの前記フィルタリングされた密度画像と、前記第2のフレームからの前記フィルタリングされた密度画像との相互相関値のピーク値に基づいて、前記少なくとも1つの変換ベクトルを決定する、請求項6記載の方法。
請求項8
前記XY平面及び前記Z平面の双方において、前記第1のフレーム及び前記第2のフレームから、前記雲状3Dデータ点群についての粗い記録を行う、請求項1記載の方法。
請求項9
前記第1のフレーム及び前記第2のフレームからの前記雲状3Dデータ点群に基づいて、細かい記録プロセスを実行する、請求項8記載の方法。
請求項10
前記細かい記録プロセスが、前記第1のフレーム及び前記第2のフレームの各々における複数の部分空間を規定するステップを含む、請求項9記載の方法。
請求項11
前記細かい記録プロセスが、選択された配置を示す雲状3Dデータ点群を含む条件を満たす前記部分空間の1つ以上を特定するステップをさらに有する、請求項10記載の方法。